import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/5 9:51
 * @description:
 */
public class Solution160 {
    //哈希集合法
    //双指针法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p = headA;
        int lenA = 0;
        int lenB = 0;
        while (p != null) {
            p = p.next;
            lenA++;
        }
        p = headB;
        while (p != null) {
            p = p.next;
            lenB++;
        }
        int lenDiff = Math.abs(lenB - lenA);
        ListNode p1 = headA;
        ListNode p2 = headB;
        if (lenA > lenB) {
            while (lenDiff-- > 0) {
                p1 = p1.next;
            }
            while (p1 != null && p2 != null) {
                if (p1 == p2) {
                    return p1;
                }
                p1 = p1.next;
                p2 = p2.next;
            }
        } else {
            while (lenDiff-- > 0) {
                p2 = p2.next;
            }
            while (p1 != null && p2 != null) {
                if (p1 == p2) {
                    return p1;
                }
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }

    public static void main(String[] args) {
        Solution160 solution = new Solution160();
        //listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
        ListNode n1 = new ListNode(4);
        ListNode n2 = new ListNode(5);
        ListNode n3 = new ListNode(6);
        ListNode n4 = new ListNode(1);
        ListNode n5 = new ListNode(8);
        ListNode n6 = new ListNode(4);
        ListNode n7 = new ListNode(5);
        n1.next = n4;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = null;
        ListNode res = solution.getIntersectionNode(n1, n2);
        System.out.println(res.val);
    }
}
